package com.lxq.LeetCode.findTheDistanceValue;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] arr1 = {1,4,2,3};
        int[] arr2 = {-4,-3,6,10,20,30};
        int d = 3;
        System.out.println(findTheDistanceValue(arr1, arr2, d));
    }

    public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int res = 0;
        Arrays.sort(arr2);
        for (int num : arr1) {
            if (binarySearch(arr2, num, d, 0, arr2.length - 1)) {
                res++;
            }
        }
        return res;
    }

    public static boolean binarySearch(int[] arr1, int tag, int d, int min, int max) {
        if (max < min) {
            return true;
        }
        int mid = min + (max - min) / 2;
        if (Math.abs(arr1[mid] - tag) <= d) {
            return false;
        }
        if (arr1[mid] > tag) {
            max = mid - 1;
        } else {
            min = mid + 1;
        }
        return binarySearch(arr1, tag, d, min, max);

    }
}
